977. Is it a Tree?

An undirected graph without loops and multiple edges is given by an adjacency matrix. Determine whether this graph is a tree.

Input. The first line contains the number of vertices n (1 ≤ n ≤ 100) in the graph. Then, an adjacency matrix of size n × n is given, where 1 indicates the presence of an edge, and 0 indicates its absence. The matrix is symmetric with respect to the main diagonal.

Output. Print “YES” if the graph is a tree, and “NO” otherwise.

Sample input

Sample output

0 1 0

1 0 1

0 1 0

YES

SOLUTION

graphs – depth first search

Algorithm analysis

A graph with n vertices is a tree if and only if:

1. The graph is connected. Start a depth-first search from the first vertex. Count the number of visited vertices during the search. If it equals n, then the graph is connected.

2. |V| = |E| + 1. If the graph is a tree, then it contains n – 1 edges.

3. The graph does not contain cycles. Start a depth-first search from the first vertex. If a back edge exists, then the graph has a cycle and is not a tree.

Satisfying conditions 1) and 2) or 1) and 3) is sufficient for the graph to be a tree.

Example

The graph provided in the example is a tree.

Algorithm realization – checking the conditions 1) and 3)

Declare the adjacency matrix of the graph g and the array used.

#define MAX 110

int m[MAX][MAX], used[MAX];

The dfs function performs a depth-first search starting from vertex v. The parent of vertex v is p. If a cycle is detected, the flag variable is set to 1.

void dfs(int v, int p)

{

If the graph is no longer a tree (flag = 1), there is no need to continue the search.

if (flag) return;

Mark the vertex v as visited.

used[v] = 1;

The vertex v is visited, increase c by 1.

c++;

The edge (v, i) will be a back edge and form a cycle if i ≠ p and vertex i is already visited (used[i] = 1). If a cycle is detected, set flag = 1. If no cycle is detected, continue the search from vertex i.

for(int i = 0; i < n; i++)

if ((i != p) && g[v][i])

if(used[i]) flag = 1; else dfs(i,v);

}

The main part of the program. Read the input data.

scanf("%d",&n);

for(i = 0; i < n; i++)

for(j = 0; j < n; j++)

scanf("%d",&g[i][j]);

Count the number of visited vertices during the depth-first search in the variable c. Set flag = 0 if there is no cycle in the graph. If a cycle is detected, flag becomes 1.

c = 0;

flag = 0;

All vertices are initially unvisited (initialize the array used with zeroes).

memset(used,0,sizeof(used));

Start the depth-first search from vertex 0. Since it is the root of the tree, it has no parent. Pass the value -1 as the second argument to the dfs function.

dfs(0,-1);

The graph is not a tree if there is a back edge (flag = 1) or if the graph is not connected (c ≠ n).

if (flag || (c != n)) printf("NO\n"); else printf("YES\n");

Algorithm realization – checking the conditions 1) and 2)

Declare the adjacency matrix of the graph g and the array used.

#define MAX 101

int g[MAX][MAX], used[MAX];

The dfs function implements depth-first search from vertex v.

void dfs(int v)

{

Mark the vertex v as visited.

used[v] = 1;

Vertex v is visited, increase c by 1.

c++;

Iterate over the vertices i, that can be reached from v. Moving from v to i is possible if:

· There is an edge (v, i), that is, g[v][i] = 1;

· The vertex i is not visited (used[i] = 0)

If both conditions are true, we continue the depth-first search from vertex i.

for (int i = 1; i <= n; i++)

if (g[v][i] && !used[i]) dfs(i);

}

The main part of the program. Read the input value of n.

scanf("%d", &n);

Count the number of edges in the graph in the variable Edges.

Edges = 0;

All vertices are initially unvisited (initialize the array used with zeroes).

memset(used, 0, sizeof(used));

Read the adjacency matrix g. Count the number of edges in the graph.

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++)

{

scanf("%d", &g[i][j]);

Edges += g[i][j];

}

Since the graph is undirected, edges (u, v) and (v, u) are considered the same. Divide the value of Edges by 2.

Edges /= 2;

Count the number of visited vertices during the depth-first search in variable c.

c = 0;

Start the depth-first search from the vertex 1.

dfs(1);

The graph is a tree if the number of edges in it equals n – 1, and also if it is connected (c = n).

if ((Edges == n - 1) && (c == n)) printf("YES\n");

else printf("NO\n");

Java realization

import java.util.*;

//import java.io.*;

public class Main

{

static int c = 0;

static int m[][], used[];

static void dfs(int v)

{

used[v] = 1; c++;

for(int i = 0; i < m.length; i++)

if (m[v][i]== 1 && used[i] == 0) dfs(i);

}

public static void main(String[] args) //throws IOException

{

Scanner con = new Scanner(System.in);

//Scanner con = new Scanner(new FileReader ("977.in"));

int n = con.nextInt();

m = new int[n][n];

used = new int[n];

Arrays.fill(used, 0);

int Edges = 0;

for(int i = 0; i < n; i++)

for(int j = 0; j < n; j++)

{

m[i][j] = con.nextInt();

Edges += m[i][j];

}

dfs(0); Edges /= 2;

if ((Edges == n - 1) && (c == n))

System.out.printf("YES");

else

System.out.printf("NO");

}

Python realization – checking the conditions 1) and 3)

The dfs function performs a depth-first search starting from vertex v. The parent of vertex v is p. If a cycle is detected, the flag variable is set to 1.

def dfs(v, p):

Declare the global variables used by the function.

global flag, c

If the graph is no longer a tree (flag = 1), there is no need to continue the search.

if flag: return

Mark the vertex v as visited.

used[v] = 1

The vertex v is visited, increase c by 1.

c += 1

for i in range(n):

if i != p and g[v][i]:

if used[i]: flag = 1

else: dfs(i, v)

The main part of the program. Read the input value of n.

n = int(input())

Count the number of visited vertices during the depth-first search in the variable c. Set flag = 0 if there is no cycle in the graph. When a cycle is detected, flag becomes 1.

c = 0

flag = 0

All vertices are initially unvisited (initialize the list used with zeroes).

used = [0] * n

Create an adjacency matrix g, initially filled with zeroes.

g = [[0] * n for _ in range(n)]

Read the input adjacency matrix.

for i in range(n):

g[i] = list(map(int, input().split()))

Start the depth-first search from vertex 0. Since it is the root of the tree, it has no parent. Pass the value -1 as the second argument to the dfs function.

dfs(0, -1)

The graph is not a tree if there is a back edge (flag = 1) or if the graph is not connected (c ≠ n).

if flag or c != n:

print("NO")

else:

print("YES")

Python realization – checking the conditions 1) and 2)

The dfs function implements depth-first search from vertex v.

def dfs(v):

global c

Mark the vertex v as visited.

used[v] = 1

The vertex v is visited, increase c by 1.

c += 1

Iterate over the vertices i, that can be reached from v. Moving from v to i is possible if:

· There is an edge (v, i), that is, g[v][i] = 1;

· The vertex i is not visited (used[i] = 0)

If both conditions are true, we continue the depth-first search from vertex i.

for i in range(1, n + 1):

if g[v][i] and not used[i]: dfs(i)

The main part of the program. Read the input value of n.

n = int(input())

Count the number of edges in the graph in the variable Edges.

Edges = 0

All vertices are initially unvisited (initialize the array used with zeroes).

used = [0] * (n + 1)

Create an adjacency matrix g, initially filled with zeroes.

g = [[0] * (n + 1) for _ in range(n + 1)]

Read the adjacency matrix g. Count the number of edges in the graph.

for i in range(1, n + 1):

g[i] = [0] + list(map(int, input().split()))

Edges += sum(g[i])

Since the graph is undirected, edges (u, v) and (v, u) are considered the same. Divide the value of Edges by 2.

Edges //= 2

Count the number of visited vertices during the depth-first search in variable c.

c = 0

Start the depth-first search from the vertex 1.

dfs(1)

The graph is a tree if the number of edges in it equals n – 1, and also if it is connected (c = n).

if Edges == n - 1 and c == n:

print("YES")

else:

print("NO")